Search results for "Bipartite graph"

Spatially-induced nestedness in a neutral model of phage-bacteria networks

2017

[EN] Ecological networks, both displaying mutualistic or antagonistic interactions, seem to share common structural traits: the presence of nestedness and modularity. A variety of model approaches and hypothesis have been formulated concerning the significance and implications of these properties. In phage-bacteria bipartite infection networks, nestedness seems to be the rule in many different contexts. Modeling the coevolution of a diverse virus¿host ensemble is a difficult task, given the dimensionality and multi parametric nature of a standard continuous approximation. Here, we take a different approach, by using a neutral, toy model of host¿phage interactions on a spatial lattice. Each …

Packing colorings of subcubic outerplanar graphs

2018

Given a graph $G$ and a nondecreasing sequence $S=(s_1,\ldots,s_k)$ of positive integers, the mapping $c:V(G)\longrightarrow \{1,\ldots,k\}$ is called an $S$-packing coloring of $G$ if for any two distinct vertices $x$ and $y$ in $c^{-1}(i)$, the distance between $x$ and $y$ is greater than $s_i$. The smallest integer $k$ such that there exists a $(1,2,\ldots,k)$-packing coloring of a graph $G$ is called the packing chromatic number of $G$, denoted $\chi_{\rho}(G)$. The question of boundedness of the packing chromatic number in the class of subcubic (planar) graphs was investigated in several earlier papers; recently it was established that the invariant is unbounded in the class of all sub…

When can an equational simple graph be generated by hyperedge replacement?

1998

Infinite hypergraphs with sources arise as the canonical solutions of certain systems of recursive equations written with operations on hypergraphs. There are basically two different sets of such operations known from the literature, HR and VR. VR is strictly more powerful than HR on simple hypergraphs. Necessary conditions are known ensuring that a VR-equational simple hypergraph is also HR-equational. We prove that two of them, namely having finite tree-width or not containing the infinite bipartite graph, are also sufficient. This shows that equational hypergraphs behave like context-free sets of finite hypergraphs.

Counting degree sequences of spanning trees in bipartite graphs: A graph‐theoretic proof

2019

Stationary states in quantum walk search

2016

When classically searching a database, having additional correct answers makes the search easier. For a discrete-time quantum walk searching a graph for a marked vertex, however, additional marked vertices can make the search harder by causing the system to approximately begin in a stationary state, so the system fails to evolve. In this paper, we completely characterize the stationary states, or 1-eigenvectors, of the quantum walk search operator for general graphs and configurations of marked vertices by decomposing their amplitudes into uniform and flip states. This infinitely expands the number of known stationary states and gives an optimization procedure to find the stationary state c…

Adjacent vertices can be hard to find by quantum walks

2018

Quantum walks have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems. Most of the papers, however, consider a search space containing a single marked element. We show that if the search space contains more than one marked element, their placement may drastically affect the performance of the search. More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk needs Ω(N) steps, that is, it has no speed-up over the classical exhaustive search. The demonstrated configurations occur for certain placements of two or more adjace…

Span-Program-Based Quantum Algorithms for Graph Bipartiteness and Connectivity

2016

Span program is a linear-algebraic model of computation which can be used to design quantum algorithms. For any Boolean function there exists a span program that leads to a quantum algorithm with optimal quantum query complexity. In general, finding such span programs is not an easy task. In this work, given a query access to the adjacency matrix of a simple graph G with n vertices, we provide two new span-program-based quantum algorithms:an algorithm for testing if the graph is bipartite that uses $$On\sqrt{n}$$ quantum queries;an algorithm for testing if the graph is connected that uses $$On\sqrt{n}$$ quantum queries.

Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem

2014

The bipartite unconstrained 0-1 quadratic programming problem (BQP) is a difficult combinatorial problem defined on a complete graph that consists of selecting a subgraph that maximizes the sum of the weights associated with the chosen vertices and the edges that connect them. The problem has appeared under several different names in the literature, including maximum weight induced subgraph, maximum weight biclique, matrix factorization and maximum cut on bipartite graphs. There are only two unpublished works (technical reports) where heuristic approaches are tested on BQP instances. Our goal is to combine straightforward search elements to balance diversification and intensification in bot…

Scalable Ellipsoidal Classification for Bipartite Quantum States

2008

The Separability Problem is approached from the perspective of Ellipsoidal Classification. A Density Operator of dimension N can be represented as a vector in a real vector space of dimension $N^{2}- 1$, whose components are the projections of the matrix onto some selected basis. We suggest a method to test separability, based on successive optimization programs. First, we find the Minimum Volume Covering Ellipsoid that encloses a particular set of properly vectorized bipartite separable states, and then we compute the Euclidean distance of an arbitrary vectorized bipartite Density Operator to this ellipsoid. If the vectorized Density Operator falls inside the ellipsoid, it is regarded as s…

Core of communities in bipartite networks

2017

We use the information present in a bipartite network to detect cores of communities of each set of the bipartite system. Cores of communities are found by investigating statistically validated projected networks obtained using information present in the bipartite network. Cores of communities are highly informative and robust with respect to the presence of errors or missing entries in the bipartite network. We assess the statistical robustness of cores by investigating an artificial benchmark network, the co-authorship network, and the actor-movie network. The accuracy and precision of the partition obtained with respect to the reference partition are measured in terms of the adjusted Ran…